package sort.LeetCode;
//215. 数组中的第K个最大元素
//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。是非降序数组，包含相等元素

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

//第一种，直接排序
/*
public class Num215_findKthLargest {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);

        return nums[nums.length - k];
    }
}
*/

//第二中，堆排，最小堆，求出前 k 个最小值，入队列后，第一个就是答案

/*

public class Num215_findKthLargest {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> queue = new PriorityQueue<>();

        for(int i : nums){
            if(queue.size() < k){
                queue.offer(i);
            }else{
                int val = queue.peek();
                if(val < i){
                    queue.poll();
                    queue.offer(i);
                }

            }

        }
        return queue.poll();
    }
}

*/

//3.利用快排的分区思想~~ O(n)

public class Num215_findKthLargest {
    private static ThreadLocalRandom random = ThreadLocalRandom.current();//产生一个随机数
    public static int val = 0;
    public static int findKthLargest(int[] nums, int k) {
        quickSortInternal(nums, 0, nums.length - 1, k);
        return nums[val];
    }
    //        快排的分区就是分区之后，分区点pivot就落在了最终位置
    //        就利用快排的分区返回值p若p ==n-k =>这个元素恰好就是第k大元素
    //        p <n - k =>要查找的元素在右半区间，右半区间继续寻找
    //        p>n-k =>要查找的元素在左半区间，左半区间继续寻找。

    private static void quickSortInternal(int[] nums, int l, int r, int k) {
        if(l >= r){
            if(l == nums.length - k){
                val = l;
            }
            return ;
        }

        int p = partition(nums, l, r, k);

        if(p == nums.length - k){
            val = p;
        }else if(p > nums.length - k) {

            quickSortInternal(nums, l, p - 1, k);
        }else {
            quickSortInternal(nums, p + 1, r, k);
        }


        return ;
    }

    private static int partition(int[] nums, int l, int r, int k) {
        int randomIndex = random.nextInt(l, r);
        swap(nums, l, randomIndex);
        int v = nums[l];

        int j = l;
        for (int i = l + 1; i <= r ; i++) {
            if(nums[i] < v){
                swap(nums, j + 1, i);
                j ++;
            }
        }
        swap(nums, l, j);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3,2,3,1,2,4,5,5,6};
        System.out.println(Arrays.toString(arr));
        int v = findKthLargest(arr, 3);
        System.out.println(v);
        System.out.println(Arrays.toString(arr));
    }
}

